<HTML>
<HEAD>
<TITLE>CS 440 Program 2</TITLE>
</HEAD>

<font size = 4>
<body bgcolor = "ffffff">

<CENTER><H2>CS 440
<BR>Program 2</H2></CENTER>

<H3><CENTER>due October 7, 2011</CENTER></H3>

<H3>The Program</H3>

For Program 2 you will write two modules of your PAXI compiler, the
<EM>scanner</EM> and the <EM>symbol table</EM>.  In order to test your
program you will also write two <EM>test drivers</EM> which exercise
these modules.

<H3>The Scanner</H3>

The scanner will be written using <EM>flex</EM>.  It will recognize as
a lexeme each of the <EM>keywords</EM> listed in the <A
href="http://cs.gmu.edu/~dnord/cs440/paxi.html">PAXI Language Definition</A> and
each of the symbols listed there except ' (single quote) and &quot;
(double quote).  It will return an integer <EM>token</EM> for each of
these lexemes.

<P>Tokens can be chosen arbitrarily (but must be non-zero).  They
<EM>must</EM> be given readable names which are defined in a header
file #included into your flex file.

<P>Your scanner must also recognize:
<UL>
<LI>identifiers
<BR>action: return token (more will be added here in Program 3)
<LI>literal integers
<BR>action: save the integer value in a global variable and return a
token
<LI>quoted strings
<BR>action: remove quote marks, add to <EM>string list</EM>, and
return token
<LI>single characters (enclosed in single quotes)
<BR>action: return token
<LI>new line characters ('\n')
<BR>action: increment line counter
<LI>comments
<BR>action: none
<LI>white space (regular expression: [ \t])
<BR>action: ignore
<LI>characters which do not match the lexical structure of PAXI
(regular expression: ".")
<BR>action: give error message and exit program.
</UL>

<H3>The String List</H3>

Whenever a quoted string is recognized it is added (without quote
marks) to a <EM>string list</EM>.  The string list must be kept in the
order in which the strings are found in the source file. I.e. when a
new string is found it is added to the <EM>end</EM> of the list.

<H3>The Symbol Table</H3>

The <EM>symbol table</EM> will be a hash table.  The simplest hash
table organization ("separate chaining" for synonyms) will work well
here.  The table's internal workings will <EM>not</EM> be visible
outside of the module in which it is defined.  Access will be through
two operations: <EM>lookup</EM> and <EM>insert</EM>.

<P><EM>Lookup</EM> will take a character string as parameter, search
the symbol table and return a pointer to a symbol table entry if one
is found having that string as its (identifier) key.  If no entry was
found lookup will return a NULL pointer.

<P><EM>Insert</EM> will create a new entry in the symbol table.
Before making the new entry it will first check to see if an entry
already exists with the same (identifier) key.  If such already exists
insert will return a value indicating that it failed, otherwise it
will return a value indicating success.

<P>Symbol table entries will have four fields:

<UL>
<LI>name
<LI>type
<LI>size
<LI>location
</UL>

The <EM>name</EM> field will hold the identifier.  The <EM>type</EM>
field will hold value <EM>variable</EM>, <EM>array</EM>,
<EM>procedure</EM>, <EM>parameter</EM>, or <EM>local variable</EM>.
<EM>Size</EM> will be 1 in the case of a (scalar) variable, the array
length in the case of an array, and the number of formal parameters in
the case of a procedure.  <EM>Location</EM> will be the address (data
store index) of a variable or array and the entry point (code store
index) for a procedure.  For Program 2 the size and location fields
will be set to 0 (this will be changed in later programs).

<H3>The Test Drivers</H3>

You will write a test driver to run your scanner and another to test
your symbol table functions.

<P>For the first test driver, you will write a program which calls the
scanner (<EM>yylex()</EM>) in a loop which terminates on end of input
(when yylex() returns 0).  Each time yylex() returns a token your
program will print out the (integer) token value.  If the token is
that for identifier, number, or string the program will also display
the recognized identifier, number, or string.  After the program has
finished scanning the input it will display the entire string list.

<P>The second test driver will display a simple menu to the user with
three options:  <EM>insert</EM>, <EM>lookup</EM>, and <EM>quit</EM>.
If the user chooses <EM>insert</EM> the program will accept an
identifier (character string) and type (as described above) and call
the symbol table's insert operation to make a new table entry.  The
test program will display whether the insertion was successful or
not.  If the user chooses <EM>lookup</EM> the program will accept an
identifier and attempt to find a symbol table entry for that entry.
If none is found a message to that effect will be displayed.  If one
is found its four fields will be displayed.  When the user chooses
<EM>quit</EM> the program will display the <EM>entire</EM> symbol
table, in a readable form, and then exit.

<H3>Opening Files</H3>

Your scanner test driver must get the name of an input file from the
user (from the command line or by prompting the user), open the file
for reading, and assign it to <EM>yyin</EM>.

yyin is declared by flex to be of type
FILE*.  This means that you should open the input file using the C
<EM>fopen()</EM> function and assign the returned pointer to yyin.  If
your program was unable to open the input file (fopen() returned a
NULL pointer) you should display a polite error message and exit.

<H3>To Hand In</H3>

As with Program 1 you will hand in your source code
and a terminal session using sample data to be provided later.

</HTML>
